#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : FindModeBinarySearchTree.py
# @Time    : 2020/9/24 14:58
# @Description:
from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        """
        Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element)
        in the given BST.
        
        Assume a BST is defined as follows:
        
        The left subtree of a node contains only nodes with keys less than or equal to the node's key.
        The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
        Both the left and right subtrees must also be binary search trees.
        
        For example:
        Given BST [1,null,2,2],
        
           1
            \
             2
            /
           2

        return [2].
        
        Note: If a tree has more than one mode, you can return them in any order.
        Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred
        due to recursion does not count).

        :param root:
        :return:
        """
        base = None
        count = 0
        maxCount = 0
        ans = []

        def update(x: int):
            nonlocal base, count, maxCount, ans
            if x == base:
                count += 1
            else:
                count = 1
                base = x
            if count == maxCount:
                ans.append(base)
            if count > maxCount:
                maxCount = count
                ans = [base]

        cur = root
        pre = None
        while cur:
            if not cur.left:
                update(cur.val)
                cur = cur.right
                continue
            pre = cur.left
            while pre.right and pre.right is not cur:
                pre = pre.right
            if not pre.right:
                pre.right = cur
                cur = cur.left
            else:
                pre.right = None
                update(cur.val)
                cur = cur.right
        return ans


if __name__ == '__main__':
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(2)
    S = Solution()
    print(S.findMode(root))
    print('done')
